#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"

#define MAX_SIZE 100

void rev_string(char *str)
{
	int n, i;
	char t;

	n = strlen(str);

	for (i = 0; i < n / 2; i++) {
		t = str[i];
		str[i] = str[n - i - 1];
		str[n - i - 1] = t;
	}
}

int is_op(char c)
{
	return c == '+' || c == '-' || c == '*' || c == '/' || c == '%';
}

int get_level(char op)
{
	switch (op)
	{
		case '+':
		case '-':
			return 1;
		case '*':
		case '/':
		case '%':
			return 2;
		default:
			return 0;
	}
}

char peek(stack_t *opstack)
{
	char data;

	if (stack_empty(opstack)) {
		return '\0';
	}

	stack_peek(opstack, &data);

	return data;
}

int main(int argc, char *argv[])
{
	char *input = argv[1];
	char prefix[MAX_SIZE] = { '\0' };
	stack_t *opstack;
	int i, j;
	int len;
	char c, data;

	len = strlen(input);
	// 逆序中缀表达式	
	rev_string(input);

	stack_init(&opstack, sizeof (char), MAX_SIZE);

	for (i = 0, j = 0; i < len; i++) {
		c = input[i];

		if (c == ')') { // 注意是输入字符串中的右括号，逆序后应为左括号，压栈
			stack_push(opstack, &c);
		} else if (c == '(') { // 注意是输入字符串中的左括号，逆序后应为右括号，弹栈
			while (!stack_empty(opstack) && peek(opstack) != ')') {
				stack_pop(opstack, &prefix[j++]);
			}
			// 弹出另一半括号
			stack_pop(opstack, &data);
		} else if (is_op(c)) { // 是运算符
			while (!stack_empty(opstack) && get_level(peek(opstack)) > get_level(c)) {
				stack_pop(opstack, &prefix[j++]); // 弹出原来栈顶优先级较低的运算符
			}
			// 压入优先级更高的运算符
			stack_push(opstack, &c);
		} else { // 运算数，直接复制
			prefix[j++] = c;
		}
	}

	// 弹出栈中剩余的所有运算符
	while (!stack_empty(opstack)) {
		stack_pop(opstack, &prefix[j++]);
	}

	prefix[j] = '\0';

	// 再倒序过来得到前缀表达式
	rev_string(prefix);

	printf("前缀表达式：%s\n", prefix);

	return 0;
}
